#pragma once
#include <vector>
#include "algorithm"
#include "unordered_map"
//重写优先级队列 可以获取优先级队列当前元素的index
namespace hj{

    //比较方式
    template<typename T>
    struct less{
        bool operator()(const T& x,const T& y)
        {
            return x<y;
        }

    };

    template<typename T>
    struct greater{
        bool operator()(const T& x,const T& y)
        {
            return x>y;
        }

    };

    template<class T,  class Compare = less<T> ,typename Hash = std::hash<T>>
    class priority_queue{

    public:

        //堆的向上调整
        void adjustUp(int child)
        {
            int parent = (child - 1) / 2; //通过child计算parent的下标
            while (child > 0)//调整到根结点的位置截止
            {
                if (_comp(_con[parent], _con[child]))//通过所给比较方式确定是否需要交换结点位置
                {
                    //将父结点与孩子结点交换
                    std::swap(_con[child], _con[parent]);
                    //继续向上进行调整
                    std::swap(mp[_con[child]],mp[_con[parent]]);//维护index

                    child = parent;
                    parent = (child - 1) / 2;
                }
                else//已成堆
                {
                    break;
                   // return child;//返回下标
                }
            }

            //return 0;
        }

        //向下调整堆
        void  adjustDown(int parent)
        {
            //获取左孩子
            int child=2*parent+1;

            while(child<_con.size())
            {
                //如果存在右子树且柚子树和做字数比较
                if(child+1<_con.size()&&_comp(_con[child],_con[child+1]))
                {
                    child++;
                }

                if(_comp(_con[parent],_con[child]))
                {
                    //将父结点与孩子结点交换
                    std::swap(_con[child], _con[parent]);
                    //继续向下进行调整
                    std::swap(mp[_con[child]],mp[_con[parent]]);//维护index
                    parent = child;
                    child = 2 * parent + 1;

                }else{
                    //return parent;//返回下标
                    break;
                    //完成调整
                }

            }

               // return _con.size();
        }

        //插入元素到队尾（并排序）
        void  push(const T& x)
        {
            _con.push_back(x);
            mp[x]=_con.size()-1;//设置index
            adjustUp(_con.size() - 1); //将最后一个元素进行一次向上调整
        }


        //弹出队头元素（堆顶元素）
        void pop()
        {
            std::swap(_con[0], _con[_con.size() - 1]);
            std::swap(mp[_con[0]], mp[_con[_con.size() - 1]]);//维护index;
            auto t=_con.back();
            _con.pop_back();
            mp.erase(t);
            adjustDown( 0); //将第0个元素进行一次向下调整
        }
        //访问队头元素（堆顶元素）
        T& top()
        {
            return _con[0];
        }

        const T &top() const {

            return _con[0];
        }

        //获取队列中有效元素个数
        size_t size() {
            return _con.size();
        }

        //判断队列是否为空
        bool empty() {
            return _con.empty();
        }

        int get_index(const T& t)
        {
            auto iter = mp.find(t);
            if (iter!=mp.end())
            {
               return iter->second;
            }

            return -1;
        }

        std::vector<T> &get_container() {
            return _con;
        }

        void container_modify(int index, T t) {
            this->_con[index] = t;
        }

    private:
        std::unordered_map<T, int, Hash> mp;
        std::vector<T> _con; //底层容器
        Compare _comp; //比较方式

    };









}